#include <stdio.h>
#include <stdlib.h>


// 双向链表的结构体
typedef struct DoubleLinkNode{
    int data;
    // 指向下一个
    struct DoubleLinkNode * next;
    // 指向上一个
    struct DoubleLinkNode * prev;
} * DoubleLinkList;


/**
 * 初始化双向链表
 * @param head
 */
void initLinkNode(DoubleLinkList head) {
    // 头节点默认指向NULL, 头节点不存储数据
    head->next = NULL;
    head->prev = NULL;
}

/**
 * 双向链表插入操作
 * @param head 头节点指针
 * @param index 位序（从1开始）
 * @param data 插入的数据
 * @return 0表示失败，1表示成功
 */
_Bool insertNode(DoubleLinkList head, int index, int data) {
    // 非法位序
    if(index < 1) {
        return 0;
    }
    struct DoubleLinkNode * p = head;
    // --index 先减然后再操作
    while(--index) {
        // 当index为0时，p指向的恰好是插入位置的前一个节点
        p = p->next;
        // index越界
        if(p == NULL) {
            return 0;
        }
    }
    // 为插入的新节点分配内存
    DoubleLinkList newNode = malloc(sizeof(DoubleLinkList));
    // 内存分配失败
    if(newNode == NULL) {
        return 0;
    }
    newNode->data = data;
    // 后继节点可能不存在
    if(p->next) {
        newNode->next = p->next;
        // 不判断，此处可能会空指针异常
        p->next->prev = newNode;
    } else {
        newNode->next = NULL;
    }
    p->next = newNode;
    newNode->prev = p;
    return 1;
}

/**
 * 链表删除操作
 * @param head 头节点指针
 * @param index 位序（从1开始）
 * @return
 */
_Bool deleteNode(DoubleLinkList head, int index) {
    //非法位序
    if(index < 1) {
        return 0;
    }
    DoubleLinkList p = head;
    // 只有头节点的时候
    if(p->next == NULL) {
        return 0;
    }
    while(--index){
        p = p->next;
        // index越界
        if(p == NULL) {
            return 0;
        }
    }
    // 记录要删除的节点后再删除
    struct DoubleLinkNode * q = p->next;
    if(q->next) {
        p->next = q->next;
        q->next->prev = p;
    } else { // 删除最后一个节点
        p->next = NULL;
    }
    // 释放内存
    free(q);
    return 1;
}

/**
 * 根据位序查找元素
 */
int findNodeData(DoubleLinkList head, int index) {
    //非法位序
    if(index < 1) {
        return 0;
    }
    DoubleLinkList p = head;
    if(p->next == NULL) {
        return INT_MAX;
    }
    while (--index) {
        p = p->next;
        if(p == NULL) {
            return INT_MAX;
        }
    }
    return p->next->data;
}

/**
 * 计算链表长度（除头节点）
 */
int getDoubleLinkListLength(DoubleLinkList head) {
    int size = 0;
    while (head->next) {
        head = head->next;
        size++;
    }
    return size;
}

/**
 * 打印数据
 */
void printDoubleLinkList(DoubleLinkList linkList) {
    while (linkList) {
        linkList = linkList->next;
        printf("%d\t", linkList->data);
    }
}

int main3() {
    struct DoubleLinkNode head;
    initLinkNode(&head);
    insertNode(&head, 1, 10);
    insertNode(&head, 1, 20);
    insertNode(&head, 3, 30);
    deleteNode(&head, 1);
    printf("%d\n", findNodeData(&head, 2));
    printf("%d\n", getDoubleLinkListLength(&head));
    printDoubleLinkList(&head);
}


